#pragma once
#include <iostream>
#include <algorithm>
using std::cout;
using std::endl;

namespace xyl
{
    template <class T>
    struct BSTNode
    {
        BSTNode(const T &data = T())
            : _left(nullptr),
              _right(nullptr),
              _data(data)
        {
        }

        BSTNode<T> *_left;
        BSTNode<T> *_right;
        T _data;
    };

    template <typename T>
    class BSTree // 左小右大
    {
        typedef BSTNode<T> Node;
        typedef Node *pNode;

    private:
        void _prevPrint(pNode root)
        {
            if (root == nullptr)
                return;
            cout << root->_data << " ";
            _prevPrint(root->_left);
            _prevPrint(root->_right);
        }

        /*寻找结点*/
        pNode find(const T &data)
        {
            pNode cur = _root;
            while (cur)
            {
                if (data < cur->_data)
                {
                    cur = cur->_left;
                }
                else if (data > cur->_data)
                {
                    cur = cur->_right;
                }
                else
                {
                    // find it.
                    return cur;
                }
            }
            return nullptr;
        }

        /*delete树*/
        void _destroy(pNode root)
        {
            if (nullptr == root)
                return;
            _destroy(root->_left);
            _destroy(root->_right);
            delete root;
        }

        /*拷贝root树，返回新树的root*/
        pNode _copy(pNode root)
        {
            // 递归
            // 递时new 结点
            // 归时连接结点
            if (root == nullptr)
                return nullptr;
            pNode newRoot = new Node(root->_data);
            newRoot->_left = _copy(root->_left);
            newRoot->_right = _copy(root->_right);
            return newRoot;
        }

        bool _find_r(pNode root, const T &data)
        {
            if (nullptr == root)
                return false;
            if (data > root->_data)
                return _find_r(root->_right, data);
            if (data < root->_data)
                return _find_r(root->_left, data);
            return true;
        }

        bool _insert_r(pNode &root, const T &data)
        {
            if (nullptr == root) // 可以插入了
            {
                root = new Node(data);
                return true;
            }
            if (data > root->_data)
                return _insert_r(root->_right, data);
            if (data < root->_data)
                return _insert_r(root->_left, data);
            // if (data == root->_data)
            return false;
        }

        bool _erase_r(pNode &root, const T &data)
        {
            if (nullptr == root)
                return false;
            if (data > root->_data)
                return _erase_r(root->_right, data);
            else if (data < root->_data)
                return _erase_r(root->_left, data);

            // 删除
            pNode del = root;
            if (nullptr == root->_left)
                root = root->_right;
            else if (nullptr == root->_right)
                root = root->_left;
            else
            {
                // 找左子树的最大节点
                pNode leftMax = root->_left;
                while (leftMax->_right)
                    leftMax = leftMax->_right;
                root->_data = leftMax->_data;
                return _erase_r(root->_left, leftMax->_data);
            }
            delete del;
            // cout << "delete success.\n";
            return true;
        }

    public:
        BSTree()
            : _root(nullptr)
        {
        }

        ~BSTree()
        {
            _destroy(_root);
            _root = nullptr;
        }

        BSTree(const BSTree<T> &x)
        {
            _root = _copy(x._root);
        }

        BSTree<T> &operator=(BSTree<T> x)
        {
            std::swap(_root, x._root);
            return *this;
        }

        /*插入结点*/
        bool insert(const T &data)
        {
            // 空树，直接申请结点
            if (nullptr == _root)
            {
                _root = new Node(data);
                return true;
            }

            // 非空树
            // 查找
            pNode cur = _root;
            pNode parent = nullptr;
            while (cur)
            {
                parent = cur;
                if (data == cur->_data)
                    return false;
                else if (data < cur->_data)
                    cur = cur->_left;
                else
                    cur = cur->_right;
            }

            // 插入
            cur = new Node(data);
            if (data < parent->_data)
                parent->_left = cur;
            else
                parent->_right = cur;
            return true;
        }

        /*删除结点*/
        bool erase(const T &data)
        {
            // 空树
            if (nullptr == _root)
                return false;

            // 非空树
            // 查找
            pNode cur = _root;
            pNode parent = nullptr;
            while (cur)
            {
                if (data == cur->_data)
                    break;

                parent = cur;
                if (data < cur->_data)
                    cur = cur->_left;
                else
                    cur = cur->_right;
            }

            // 分情况删除
            // 1.cur为空，无法删除
            if (nullptr == cur)
                return false;

            // 2.cur只有左孩子或无孩子
            if (nullptr == cur->_right)
            {
                if (parent == nullptr)
                    _root = cur->_left;
                else if (parent->_left == cur)
                    parent->_left = cur->_left;
                else
                    parent->_right = cur->_left;
                delete cur;
            }
            // 3.cur只有右孩子
            else if (nullptr == cur->_left)
            {
                if (parent == nullptr)
                    _root = cur->_right;
                else if (parent->_left == cur)
                    parent->_left = cur->_right;
                else
                    parent->_right = cur->_right;
                delete cur;
            }
            // 3.cur有左、右孩子
            else
            {
                // 查找cur右子树的最小结点
                pNode rightParent = cur;
                pNode rightMin = cur->_right;
                while (rightMin->_left)
                {
                    rightParent = rightMin;
                    rightMin = rightMin->_left;
                }
                // 替换并删除
                cur->_data = rightMin->_data;
                if (rightParent->_right == rightMin)
                    rightParent->_right = rightMin->_right;
                else
                    rightParent->_left = rightMin->_right;
                delete rightMin;
            }
            return true;
        }

        /*前序遍历*/
        void prevPrint()
        {
            _prevPrint(_root);
            cout << endl;
        }

        /*递归查找*/
        bool find_r(const T &data)
        {
            return _find_r(_root, data);
        }

        /*递归插入数据*/
        bool insert_r(const T &data)
        {
            return _insert_r(_root, data);
        }

        /*递归删除数据*/
        bool erase_r(const T &data)
        {
            return _erase_r(_root, data);
        }

    private:
        pNode _root;
    };

    void t1()
    {
        BSTree<int> t;
        t.insert(8);
        t.insert(3);
        t.insert(10);
        t.insert(1);
        t.insert(6);
        t.insert(7);
        t.insert(4);
        t.insert(14);
        t.insert(13);

        t.prevPrint();

        t.erase(10);
        t.erase(14);
        t.erase(13);
        t.erase(8);
        t.prevPrint();

        if (t.find_r(3))
        {
            cout << "find 3\n";
        }
    }

    void t2()
    {
        BSTree<int> t;
        int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
        for (auto e : a)
        {
            t.insert_r(e);
        }
        t.prevPrint();

        t.erase_r(10);
        t.prevPrint();
        t.erase_r(14);
        t.prevPrint();
        t.erase_r(13);
        t.prevPrint();
        t.erase_r(8);
        t.prevPrint();
        t.erase_r(3);
        t.prevPrint();
    }

    void t3()
    {
        BSTree<int> t;
        int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
        for (auto e : a)
            t.insert_r(e);

        BSTree<int> t2(t);

        t.prevPrint();
        t2.prevPrint();

        t2.insert(100);
        BSTree<int> t3;
        t3 = t2;
        t3.prevPrint();
    }
}